package 力扣.堆;

import java.util.*;

public class 查找和最小的k对数字373 {
    public static void main(String[] args) {
        int[] nums1 = {1,7,11};
        int[] nums2 = {2,4,6};
        int k = 3;
        List<List<Integer>> lists = kSmallestPairs2(nums1, nums2, k);
        System.out.println(lists);
    }

    /**虽然仍然是TOPK问题
     * 但是是‘升序数组’，所以使用极小堆即可

     ### 通俗原理
     假设小明有两组水果：苹果和橙子，
     而这些水果的新鲜程度都是不一样的，小明将这些水果按其新鲜程度进行排序(注意苹果和橙子分别在不同区域)。此时小明想分别吃掉一个最新鲜的苹果和橙子，小明肯定先从
     * @param k
     * @return
     */
    public static List<List<Integer>> kSmallestPairs2(int[] A, int[] B, int k) {
        if (A == null || B == null || A.length == 0 || B.length == 0 || k <= 0) {
            return new ArrayList<>();
        }
        final int N = A.length;
        final int M = B.length;

        // java小堆
        Queue<Node> Q = new PriorityQueue<>((v1, v2) -> A[v1.i] + B[v1.j] - A[v2.i] - B[v2.j]);

        for (int i = 0; i < N; i++) {//遍历数组A，取出所有的元素，分别让其和0配对，组成k对二元组
            Q.add(new Node(i, 0));//(数组A的索引i，0)
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < k && !Q.isEmpty(); i++) {//再比较k次，
            Node p = Q.poll();
            ans.add(Arrays.asList(A[p.i], B[p.j]));//(数组A的元素，数组B的元素) Node中存的都是索引（因为数组A、B都是有序的）
            if (p.j + 1 < M) {//判断是否越界
                Q.add(new Node(p.i, p.j + 1));
            }
        }

        return ans;
    }
    static class Node {
        public int i;
        public int j;

        public Node(int a, int b) {
            i = a;
            j = b;
        }
    }


    public List<List<Integer>> kSmallestPairs3(int[] nums1, int[] nums2, int k) {
        if (nums1 == null || nums2 == null || k == 0){
            return new ArrayList<>();
        }
        PriorityQueue<Integer[]> priorityQueue = new PriorityQueue<Integer[]>(new Comparator<Integer[]>() {
            @Override
            public int compare(Integer[] o1, Integer[] o2) {
                return (nums1[o1[0]] + nums2[o1[1]]) - (nums1[o2[0]] + nums2[o2[1]]);//小根堆
            }
        });
        for (int i = 0; i < nums1.length; i++) {
            priorityQueue.offer(new Integer[]{i,0});
        }
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums2.length || !priorityQueue.isEmpty(); i++) {
            Integer[] te = priorityQueue.poll();
            ans.add(Arrays.asList(nums1[te[0]],nums2[te[1]]));
            if (te[1] < nums2.length - 1){
                priorityQueue.offer(new Integer[]{te[0],te[1] + 1});
            }
            if (ans.size() == k){
                return ans;
            }
        }
        return ans;

    }
}
